//你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。 
//
// 我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
//输出：[20,24]
//解释： 
//列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
//列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
//列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
// 
//
// 示例 2： 
//
// 
//输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
//输出：[1,1]
// 
//
// 示例 3： 
//
// 
//输入：nums = [[10,10],[11,11]]
//输出：[10,11]
// 
//
// 示例 4： 
//
// 
//输入：nums = [[10],[11]]
//输出：[10,11]
// 
//
// 示例 5： 
//
// 
//输入：nums = [[1],[2],[3],[4],[5],[6],[7]]
//输出：[1,7]
// 
//
// 
//
// 提示： 
//
// 
// nums.length == k 
// 1 <= k <= 3500 
// 1 <= nums[i].length <= 50 
// -105 <= nums[i][j] <= 105 
// nums[i] 按非递减顺序排列 
// 
// Related Topics 贪心 数组 哈希表 排序 滑动窗口 堆（优先队列） 
// 👍 311 👎 0

package leetcode.editor.cn;

import algorithms.question.class19.Code4_最小区间;

import java.util.List;
import java.util.PriorityQueue;

/**
 * Java：最小区间
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P632_SmallestRangeCoveringElementsFromKLists {
    public static void main(String[] args) {
        Solution solution = new P632_SmallestRangeCoveringElementsFromKLists().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public int[] smallestRange(List<List<Integer>> nums) {
            if (nums == null || nums.size() == 0) {
                return null;
            }
            // 按value由小到大
            PriorityQueue<Info> queue = new PriorityQueue<>(nums.size(), (a, b) -> a.value - b.value);
            // help 主要是取最大值
            PriorityQueue<Info> help = new PriorityQueue<>(nums.size(), (a, b) -> b.value - a.value);
            // 每个数先放第一个数进去
            for (int i = 0; i < nums.size(); i++) {
                queue.offer(new Info(nums.get(i).get(0), i, 0));
                help.offer(new Info(nums.get(i).get(0), i, 0));
            }
            int[] res = new int[2];
            res[1] = Integer.MAX_VALUE;
            while (true) {
                // 比较上一个
                Info first = queue.poll();
                Info last = help.peek();
                help.remove(first);
                if (last.value - first.value < res[1] - res[0]) {
                    res[0] = first.value;
                    res[1] = last.value;
                }
                List<Integer> fromList = nums.get(first.from);
                // 到最后一个了，跳出循环
                if (first.index == fromList.size() - 1) {
                    break;
                }
                // 后面还有元素，加进来
                queue.offer(new Info(fromList.get(first.index + 1), first.from, first.index + 1));
                help.offer(new Info(fromList.get(first.index + 1), first.from, first.index + 1));
            }
            return res;
        }

        /**
         * 存放值和所在的list
         */
        private class Info {
            int value;
            int from;
            int index;

            public Info(int value, int from, int index) {
                this.value = value;
                this.from = from;
                this.index = index;
            }

            @Override
            public boolean equals(Object obj) {
                if (!(obj instanceof Info)) {
                    return false;
                }
                Info info = (Info) obj;

                return info.value == value && info.from == from && info.index == index;
            }
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}